package com.lry.basic.algorithm.dp;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/6/19
 */

/**
 * 01背包
 */
public class Bag {
    static int n=4;//物品数量
    static int w[]=new int[]{1,1,2,3};//重量
    static int v[]=new int[]{1,2,3,4};//价值
    static int W=5;//背包体积
    //从第i个物品开始选择总重不超过j的物品
    static int rec(int i,int j){
        if(i==n){
            return 0;
        }else if(j<w[i]){
            return rec(i+1,j);
        }else{
            return Math.max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);
        }
    }

    public static void main(String[] args) {
        System.out.println(rec(0, W));
//        System.out.println(dp());
//        System.out.println(dp1());
//        System.out.println(dp2());
//        System.out.println(dp3());
    }

//    dp[i][j]从第i个物品开始选择总重不超过j的物品
    static int dp(){
        int dp[][]=new int[n+1][W+1];
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<=W;j++){
                if(j<w[i]){
                    dp[i][j] = dp[i+1][j];
                }else{
                    dp[i][j] = Math.max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
                }
            }
        }
        return dp[0][W];
    }

// dp[i+1][j] 前i个物品里面选择总重不超过j的物品
    public static int dp1(){
        int dp[][]=new int[n+1][W+1];
        for(int i=0;i<n;i++){
            for(int j=0;j<=W;j++){
                if(j<w[i]){
                    dp[i+1][j] = dp[i][j];
                }else{
                    dp[i+1][j] = Math.max(dp[i][j], dp[i][j-w[i]]+v[i]);
                }
            }
        }
        return dp[n][W];
    }

    //完全背包 dp[i][j]从第i个物品开始选择总重不超过j的物品
    static int dp2(){
        int dp[][]=new int[n+1][W+1];
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<=W;j++){
                if(j<w[i]){//不能选
                    dp[i][j] = dp[i+1][j];
                }else{//选了还可以再选
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-w[i]]+v[i]);
                }
            }
        }
        return dp[0][W];
    }

    //完全背包
    // dp[i+1][j] 前i个物品里面选择总重不超过j的物品
    public static int dp3(){
        int dp[][]=new int[n+1][W+1];
        for(int i=0;i<n;i++){
            for(int j=0;j<=W;j++){
                if(j<w[i]){
                    dp[i+1][j] = dp[i][j];
                }else{
                    dp[i+1][j] = Math.max(dp[i][j], dp[i+1][j-w[i]]+v[i]);
                }
            }
        }
        return dp[n][W];
    }



}
